package com.wang;

/**
 * 0-1背包问题
 * @author yandong
 */
public class Knapsack {

    /**
     * 二维数组实现0-1背包
     * @param weights 物品重量数组
     * @param values 物品价值数组
     * @param capacity 背包最大容量
     * @return 能装入的最大价值
     */
    public static int solveWith2dArray(int[] weights, int[] values, int capacity) {
        // 检查输入合法性
        if (weights == null || values == null || weights.length != values.length || capacity < 0) {
            return 0;
        }

        int n = weights.length;
        // dp[i][j]表示前i个物品在容量为j的背包中能获得的最大价值
        int[][] dp = new int[n + 1][capacity + 1];

        // 遍历物品
        for (int i = 1; i <= n; i++) {
            // 遍历背包容量
            for (int j = 0; j <= capacity; j++) {
                // 不选第i个物品，价值与前i-1个物品相同
                dp[i][j] = dp[i - 1][j];

                // 若能放下第i个物品，考虑选或不选的最大值
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        return dp[n][capacity];
    }

    /**
     * 一维数组实现0-1背包（空间优化）
     * @param weights 物品重量数组
     * @param values 物品价值数组
     * @param capacity 背包最大容量
     * @return 能装入的最大价值
     */
    public static int solveWith1dArray(int[] weights, int[] values, int capacity) {
        // 检查输入合法性
        if (weights == null || values == null || weights.length != values.length || capacity < 0) {
            return 0;
        }

        int n = weights.length;
        // dp[j]表示容量为j的背包能获得的最大价值
        int[] dp = new int[capacity + 1];

        // 遍历物品
        for (int i = 0; i < n; i++) {
            // 遍历背包容量（从大到小，防止物品被重复使用）
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        return dp[capacity];
    }

    public static void main(String[] args) {
        // 测试案例
        int[] weights = {2, 3, 4, 5};  // 物品重量
        int[] values = {3, 4, 5, 6};   // 物品价值
        int capacity = 8;              // 背包容量

        int maxValue2D = solveWith2dArray(weights, values, capacity);
        int maxValue1D = solveWith1dArray(weights, values, capacity);

        System.out.println("二维数组实现的最大价值: " + maxValue2D);  // 输出: 10
        System.out.println("一维数组实现的最大价值: " + maxValue1D);  // 输出: 10
    }
}

